The present invention relates to a method of and an apparatus for optimizing the placement of circuit elements on a substrate.
In a case where a multiplicity of circuit modules having correlation with one another are arranged on a single printed circuit board, or a multiplicity of circuits elements having correlation with one another are formed on a single semiconductor substrate to produce a semiconductor device such as a large scale integration circuit (LSI), it is necessary to determine the positions of the circuit modules or circuit elements so that an evaluation function has an optimal value (for example, the total wiring length among the circuit modules or circuit elements becomes shortest or the number of crossings of wiring conductors becomes minimum), thereby reducing manufacturing cost and improving an operation speed.
FIG. 1 is a flow chart showing the steps of a procedure used in the conventional iterative improvement method for finding the optimal placement. In a case where the optimal placement of circuit elements on an LSI is determined by the iterative improvement method, a value N indicating the number of repetitions of calculation is first set in step 1. Then, the initial positions of the circuit elements are set by using pseudo-random numbers (step 2). Next, a pair of circuit elements are selected from all the circuit elements (step 3). The manufacturing cost of the selected circuit elements for a case where the selected circuit elements exchange positions with each other, is calculated (step 4). It is checked whether or not the manufacturing cost is improved by the above exchange of positions (step 5). When it is judged that the manufacturing cost of the selected circuit elements is improved, that is, when it is judged in the step 5 that a value obtained by subtracting the manufacturing cost of the selected circuit elements prior to the exchange of positions from the manufacturing cost of the selected circuit elements which have exchanged positions with each other, is negative, the selected circuit elements exchange positions with each other (step 6), and then the processing in the step 3 is again carried out. When it is judged in the step 5 that the manufacturing cost of the selected circuit elements is not improved, the processing in step 7 is carried out. In the step 7, a value C indicative of the contents of a counter is incremented by one. In step 8, it is checked whether or not the value C is greater than the value N (which is set in the step 1). When the value C is not greater than the value N, the processing in the steps 1 to 7 is again carried out. When the value C is greater than the value N, the improved placement of circuit elements is delivered (step 9).
The prior art relating to the execution of the iterative improvement method by a digital computer of the parallel processing type, is disclosed in, for example, JP-A-62-93,760, JP-A-62-243,071 and JP-A-63-121,978.
Further, a related art of this kind is disclosed in a U.S. patent application Ser. No. 492,906 filed by the same assignee (U.S. Pat. No. 5,144,563) and corresponding to a Japanese patent application (Appl. No. 1-62,215).
As mentioned above, according to the conventional placement optimizing method, a pair of circuit elements are selected, and it is checked whether or not the manufacturing cost of the selected circuit elements is improved when the selected circuit elements exchange positions with each other, to find favorable placement of circuit elements. The favorable placement does not always mean the optimal placement, but may merely correspond to a local minimum of an energy function. In other words, it may be possible to improve the favorable placement.
Further, according to the conventional placement optimizing method, the number of arithmetic operations is exponentially increased as the circuit scale of an LSI or others is larger, and it is impossible to perform a vast number of arithmetic operatons in a short time.
Recently, it has been known that a neural network can be used to find a combination of optimal solutions, and models of the neural network have been proposed by Hopfield et al. (refer to U.S. Pat. No. 4,719,591).